
<!-- saved from url=(0051)http://susy.ic.unicamp.br:9999/mc202d/04/enunc.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">


   <title>Laboratorio 04</title>
   

</head><body bgcolor="#ff9933" text="#000000"> 

<h3>Instituto de Computação da UNICAMP</h3>

<h3>Disciplina MC202 - Estrutura de Dados - Turma D</h3>

<h3>Primeiro Semestre de 2011</h3>

<h3>Laboratório Nº 04</h3>

<table>
	<tbody><tr><td><i>Prof.</i></td> <td><i>Hélio Pedrini</i></td></tr>
</tbody></table>
<table>
	<tbody><tr><td><i>Monitores:</i></td><td><i>Maikon Cismoski dos Santos - PED</i></td></tr>
	<tr><td></td><td><i>Davi Kooji Uezono - PAD</i></td></tr>
</tbody></table>
<hr>

<h2>Enunciado</h2>

<p align="justify">Campo minado é um jogo popularmente conhecido, disponível em diferentes plataformas, tais como Windows e Linux.  O objetivo do jogo é revelar um campo de minas sem que nenhuma seja detonada.
</p>
<p align="justify">O jogo consiste em uma matriz <em>m</em> x <em>n</em> de elementos, sendo <em>m</em> o número de colunas e <em>n</em> o número de linhas. Cada elemento da matriz armazena um dos seguintes caracteres:
</p>
<ul>
	<li><em>#</em> – elemento não revelado.
	</li>
	<li><em>*</em> – mina
	</li>
	<li><em>0</em> – elemento revelado que não possui minas adjacentes.
	</li>
	<li><em>Número &gt; 0</em> – elemento revelado. O número indica a quantidade de minas adjacentes.
	</li>
</ul>


<p align="justify">Cada elemento da matriz ao ser revelado pode resultar em uma das seguintes ações:
</p>

<ol>
	<li><em>O elemento revelado é uma mina</em> – O jogo acaba, o jogador perde.
	</li>
	<li><em>O elemento possui minas adjacentes</em> – O número de minas na vizinhança-8 do elemento relevado é impresso.
	</li>
	<li><em>O elemento não possui minas adjacentes</em> – O jogo revela automaticamente todos os elementos adjacentes que <strong>não são minas</strong>. Esta operação é realizada até encontrar elementos que possuam minas adjacentes ou até que não exista mais elementos a serem revelados.
	</li>
</ol>



<p align="justify">Uma jogada só é considera válida se o elemento da matriz referente à jogada ainda não foi revelado e o jogo ainda não possui um ganhador ou perdedor. O resultado do jogo pode ser três: ganhou, perdeu ou indefinido. O resultado é indefinido quando o número de jogadas for insuficiente para definir um ganhador ou perdedor. Quando todos os elementos da matriz são revelados, com exceção das minas, o jogador ganha.
</p>


<p align="justify">Escreva um programa em C que implementa o jogo campo minado. Dada uma matriz <em>m</em> x <em>n</em> de entrada contendo a localização das minas, o programa deve imprimir na saída a quantidade de minas, jogadas válidas realizadas, número de elementos revelados, resultado do jogo e a matriz resultante.
</p>


<p align="justify">O código deve possuir obrigatoriamente uma função <strong>recursiva</strong> chamada <em>revelar</em>, que implementa a ação número 3 detalhada acima. A função deve possuir a seguinte estrutura:
</p>

<pre>	<strong>int</strong> revelar(...)
</pre>

<p align="justify">A função deve retornar um inteiro com a quantidade de elementos da matriz revelados para uma jogada arbitrária. Os parâmetros da função podem ser definidos livremente.
</p>



<h2>Entrada</h2>

<p align="justify">O programa possui como entrada um arquivo texto, o qual deve ser lido pela <b>entrada padrão</b>. Alguns exemplos de entrada são ilustrados a seguir.
</p>

<div align="center">
<table border="1" cellpadding="1" cellspacing="1"><tbody>

<tr><td><strong>Entrada 1</strong></td><td><strong>Entrada 2</strong></td><td><strong>Entrada 3</strong></td><td><strong>Entrada 4</strong></td></tr>

<tr valign="top">
<td><pre>10 5
######*###
##########
####*#####
#####*####
***#######
1 1
</pre></td>
 
<td><pre>10 5
######*###
##########
####*#####
#####*####
***#######
1 1
5 10
</pre></td>

<td><pre>10 5
######*###
##########
####*#####
#####*####
***#######
1 1
5 10
3 6
4 5
5 4
5 5
5 6
</pre></td>

<td><pre>10 5
######*###
##########
####*#####
#####*####
***#######
1 1
3 5
5 10
3 6
4 5
5 4
5 5
5 6
</pre></td>
</tr>

</tbody></table>
</div>

<p align="justify">A primeira linha possui dois números <em>m</em> e <em>n</em>, que são o número de colunas e linhas da matriz de entrada, respectivamente. As próximas <em>n</em> linhas armazenam a matriz do jogo e as demais linhas as jogadas, sendo uma jogada por linha. Cada jogada é formada por dois números (posição na matriz), sendo o primeiro a linha da matriz e o segundo a coluna.
</p>



<h2>Saída</h2>

<p align="justify">O programa deve imprimir na <b>saída padrão</b> as seguintes informações: quantidade de minas, jogadas válidas realizadas,  número de elementos revelados, resultado do jogo e a matriz resultante.
</p>

<p align="justify">Alguns exemplos de saída para as entradas mostradas na seção anterior são dados a seguir.
</p>


<div align="center">
<table border="1" cellpadding="1" cellspacing="1"><tbody>

<tr><td><strong>Saída 1</strong></td><td><strong>Saída 2</strong></td><td><strong>Saída 3</strong></td><td><strong>Saída 4</strong></td></tr>

<tr valign="top">
<td><pre>Minas: 6
Jogadas: 1
Revelados: 20
Resultado: ?
000001####
000112####
0001######
2322######
##########
</pre></td>
 
<td><pre>Minas: 6
Jogadas: 2
Revelados: 39
Resultado: ?
000001#100
0001121100
0001##1000
2322##1000
######1000
</pre></td>

<td><pre>Minas: 6
Jogadas: 7
Revelados: 44
Resultado: =)
000001#100
0001121100
0001#21000
23222#1000
###1111000
</pre></td>

<td><pre>Minas: 6
Jogadas: 2
Revelados: 21
Resultado: =(
000001*###
000112####
0001*#####
2322#*####
***#######
</pre></td>
</tr>

</tbody></table>
</div>

<p align="justify">Os resultados dos jogos são expressos por “?”, “=)” e “=(”, que significam indefinido, ganhou e perdeu, respectivamente.
</p>

<p align="justify">Note que, na saída 4, o jogador perde e todas as minas são mostradas. Além disso, este resultado é identificado na segunda jogada e as demais jogadas não são realizadas.
</p>
<p align="justify">O programa deve imprimir a saída exatamente como
especificado acima, não deixe espaços em branco ou quebras de linha adicionais.
</p>

<h2>Observações</h2>
<ul>
<li>O programa deve ser escrito em linguagem C.
</li><li>A função <em>revelar</em> deve ser recursiva. Caso a função <em>revelar</em> não esteja presente no código ou esta seja implementada de forma não recursiva, a nota para este laboratório será igual a zero.
</li><li>Não é permitido o uso do comando <em>goto</em>.
</li><li>Não é permitido o uso de variáveis globais.
</li><li>A memória da matriz ou do vetor que armazena a entrada do programa deve ser alocada dinamicamente. 
</li><li>O nome do arquivo para a submissão deve ter o nome lab04_ra######.c, onde os '#' representam os dígitos do seu RA.
</li><li>Toda a memória que for alocada deve ser liberada.
</li><li>A data de entrega é 25 de abril de 2011, às 23h59.
</li><li>O número máximo de submissões é 20.
</li></ul>

<h2>Links</h2>
<p>
<a href="http://www.ic.unicamp.br/~cismoski/mc202d/atendimento.html">Agendar atendimento</a>
</p>

<p>
<a href="http://www.ic.unicamp.br/~cismoski/mc202d/avaliacao.html">Critérios de avaliação</a>
</p>

<p>
<a href="http://www.ic.unicamp.br/~cismoski/mc202d/notas.html">Notas</a>
</p>

<hr>
<small><i>12/abril/2011</i></small>
</body></html>